import java.util.HashMap;
import java.util.Map;

public class StateMachine {
    private Map<String, Map<Character, String>> states = new HashMap<>();
    private String startState;
    private boolean[] endStates;

    public void addState(String state, Map<Character, String> transitions, boolean endState) {
        states.put(state, transitions);
        if (endStates == null) {
            endStates = new boolean[256]; // Assuming ASCII characters
        }
        if (endState) {
            endStates[state.charAt(0)] = true;
        }
    }

    public void setStart(String state) {
        this.startState = state;
    }

    public String run(String inputs) {
        String currentState = startState;
        for (int i = 0; i < inputs.length(); i++) {
            char input = inputs.charAt(i);
            if (states.containsKey(currentState)) {
                Map<Character, String> transitions = states.get(currentState);
                if (transitions.containsKey(input)) {
                    currentState = transitions.get(input);
                } else {
                    return "Invalid input";
                }
            } else {
                return "State not found";
            }
        }
        if (endStates != null && endStates[currentState.charAt(0)]) {
            return "Reached end state";
        } else {
            return "Did not reach end state";
        }
    }

    public static void main(String[] args) {
        StateMachine sm = new StateMachine();

        // Add states and transition rules
        Map<Character, String> transitionsA = new HashMap<>();
        transitionsA.put('0', "B");
        transitionsA.put('1', "C");
        sm.addState("A", transitionsA, false);

        Map<Character, String> transitionsB = new HashMap<>();
        transitionsB.put('0', "A");
        transitionsB.put('1', "D");
        sm.addState("B", transitionsB, true);

        Map<Character, String> transitionsC = new HashMap<>();
        transitionsC.put('0', "D");
        transitionsC.put('1', "A");
        sm.addState("C", transitionsC, false);

        Map<Character, String> transitionsD = new HashMap<>();
        transitionsD.put('0', "C");
        transitionsD.put('1', "B");
        sm.addState("D", transitionsD, false);

        // Set start state
        sm.setStart("A");

        // Run the state machine
        String inputs = "0101";
        String result = sm.run(inputs);
        System.out.println(result); // Output result
    }
}

